IA. Field of the Invention
This invention relates to terrabit switches for use in applications like electronic and optical media. Specifically, this invention relates to a round robin greedy scheduling algorithm. This invention is embodied in methods for scheduling and a terrabit switching system that implements the round robin greedy scheduling algorithm.
IB. Background of the Invention
With the growing demand for bandwidth there is an increasing need for terabit switching. see M. Beshai, and E. Miinter, xe2x80x9cMulti-tera-bit/s switch based on burst transfer and independent shared buffers,xe2x80x9d ICC""95, pp. 1724-1730, N. McKeown et al., xe2x80x9cThe tiny tera: a packet switch core,xe2x80x9d IEEE Micro, vol. 171, January-February 1997, pp. 26-33, and W. D. Zhong, Y. Shimazu, M. Tsukuda, and K. Yukimatsu, xe2x80x9cA modular Tbit/s TDM-WDM photonic ATM switch using optical buffers,xe2x80x9d IEICE Transactions on Communications, vol. E77-B, no. 2, February 1994, pp. 190-196. Optical switching core (which can be viewed as a logical cross bar switch) with electronic control is an attractive candidate for high capacity switches. At a line rate of 10 Gb/s, a 64 byte cell/packet has to be processed within 40 ns.
An important issue faced by practitioners in the field is how to make fast scheduling decisions that will use the optical core efficiently. Switch design in such a case may involve input buffering, output buffering or both. In a switch with output buffering, the output buffers require access speed greater than the total switch throughput. Alternatively, a knockout architecture is employed in order to decrease the required output buffer speed, where a limited number of cells are accepted by the output buffer and the rest are dropped. An optical knockout switch has been proposed in, Zhong, Y. Shimazu, M. Tsukuda, and K. Yukimatsu, xe2x80x9cA modular Tbit/s TDM-WDM photonic ATM switch using optical buffers,xe2x80x9d IEICE Transactions on Communications, vol. E77-B, no. 2, February 1994, pp. 190-196. The complexity of optical knockout switching is high since each output requires several optical reverse Banyan networks and optical buffers.
Switches with input buffering use buffers more efficiently, and need memory bandwidth of only twice the line rate. In a simple scheme with input buffering, all inputs make requests to transmit packets that are at the head of their queues. If two or more inputs make requests for the same output, one of them is chosen randomly. It was shown in, see M. J. Karol, M. G. Hluchyj, and S. P. Morgan, xe2x80x9cInput vs. output queuing on a space-division packet switch,xe2x80x9d IEEE Transactions on Communications, vol. COM-35, no. 12, December 1987, pp. 1347-1356 that input buffering algorithm leads to a throughput of 0.587 under uniform traffic condition. The efficiency further decreases in the case of non-uniform traffic. In several other scheduling schemes, packets other than the HOL (head of line) packets contend for output ports. See R. Fan, M. Akiyama, and Y. Tanaka, xe2x80x9cAn input buffer-type ATM switching using schedule comparison,xe2x80x9d Electronics and Communications in Japan: Part I, vol. 74, no. 11, 1991, pp.17-25; S. Motoyama, D. W. Petr, and V. S. Frost, xe2x80x9cInput-queued switch based on a scheduling algorithm,xe2x80x9d Electronics Letters, vol. 31, no. 14, July 1995, pp. 1127-1128; and H. Obara, xe2x80x9cOptimum architecture for input queuing ATM switches,xe2x80x9d Electronics Letters, vol. 27, no. 7, March 1991, pp. 555-557. During each time slot, an input issues requests to several outputs. With just 4 requests per time slot, an efficiency approaching 1 is achieved. However, in such a scheme at high speeds multiple request/acknowledgements for scheduling cannot be processed within one time slot (where a slot represents a packet transmission time). Also, for the non-uniform traffic with hot-spots, the performance may degrade since inputs independently decide which outputs they are going to request.
The switch performance can be improved if the switch controller knows the states of all input-output queues. Such information enables the switch controller to increase the number of simultaneous transmissions in each time slot. In the SLIP protocol, the outputs independently issue grants to the inputs, which leads to some inefficiency. see N. McKeown, P. Varaiya, J. Walrand, Scheduling cells in an input-queued switch,xe2x80x9d Electronic Letters, vol. 29, no. 25, December 1993, pp. 2174-2175. Better coordination between inputs is achieved by the algorithms discussed in, see D. Guo, Y. Yemini, Z. Zhang, xe2x80x9cScalable high-speed protocols for WDM optical star networks,xe2x80x9d IEEE INFOCOM""94. However, these algorithms have a disadvantage that they require many time slots to make scheduling decisions.
It is an objective of the present invention to solve the above-mentioned problems in the conventional technologies. Specifically it is an objective of the present invention to provide a method for making scheduling decisions in a terabit switch that will efficiently use the optical core. It is a further objective of the present invention to provide a pipeline architecture that performs a round-robin greedy scheduling while providing good performance and fulfilling stringent timing requirements without internal speedups.
In order to meet the above objectives there is provided a method for determining a time slot in a Nxc3x97N crossbar switch for a round robin greedy scheduling protocol, comprising N logical queues corresponding to N output ports, the input for the protocol being a state of all the input-output queues, output of the protocol being a schedule, the method comprising: choosing input corresponding to i=(constantxe2x88x92kxe2x88x921) mod N, stopping if there are no more inputs, otherwise choosing the next input in a round robin fashion determined by i=(i+1)mod N; choosing an output j such that a pair (i,j) to a set C={(i,j)| there is at least one packet from I to j}, if the pair (i,j) exists removing i from the set of inputs and j from a set of outputs; and adding the pair (i,j) to the schedule and repeating the steps; removing i from a set of inputs and repeating the steps if the pair (i,j) does not exist; Another aspect of this invention is a method of scheduling wherein in each time slot N distinct schedules are in progress simultaneously for N distant future time slots, the method comprising; making a specific future time slot available to input for scheduling in a round-robin fashion; selecting an output for a kth time slot in future, by an input i; starting a schedule for the kth time slot in future; determining a next input (I+1) mod N and sending to the next input remaining outputs that are free to receive packets during the kth time slot.
Preferably if an input i is the last input to complete a schedule for the kth time slot, it selects an output (if feasible) and sends a modified output set to a next input; and if the input I completes a schedule for the kth time slot it does not send the output set to the next input.
Still preferably an input that does not receive a modified set of outputs from a previous input starts a new schedule.
Another aspect of the present invention is a method of pipelined round robin greedy scheduling for odd number of inputs wherein an i th time slot is completed using a process comprising: Initializing k(0,1)=k(1,1)= . . . k(Nxe2x88x921,1)=0, const=N+1, wherein, k(i,I) greater than 0 is the time slot for which input i reserves an output in Ith time slot, iI=(constxe2x88x92Nxe2x88x921) mod N denotes an input that starts a new schedule in Ith time slot, and k(i,I)=0 implies that the action of input i in time slot I is suppressed; setting OI+N={O, 1, . . . ,Nxe2x88x921}, k(II,I)=I+N, k(i,I)=k((ixe2x88x921)mod N,Ixe2x88x921) for 0xe2x89xa6ixe2x89xa6Nxe2x88x921 and ixe2x89xa0ii, choosing one output j at input i, 0xe2x89xa6ixe2x89xa6Nxe2x88x921, in a round-robin fashion from the set Ok(i,1) for which it has a packet to send, provided that k(i,I)xe2x89xa00 and excluding j from Ok(i,I); storing the address, at input i, 0xe2x89xa6ixe2x89xa6Nxe2x88x921, of the chosen output in its connection memory at location k(i, I)mod N and moving a head of line (HOL) packet from a corresponding receive input-output queue to separate transmit input-output queue; forwarding the set Ok(iI) at Input i, 0xe2x89xa6ixe2x89xa6Nxe2x88x921 and ixe2x89xa0(iixe2x88x922)mod N, to the next input (i+1)mod N; establishing a cross bar connection between the input i 0xe2x89xa6ixe2x89xa6Nxe2x88x921 and output whose address is read from location (I mod (N+1)) of the input i""s connection memory; and transmitting the reserved packet at the head of the scheduled transmit input-output queue i through the switch core for each input i, 0xe2x89xa6ixe2x89xa6Nxe2x88x921.
Preferably multicast scheduling is incorporated in round-robin greedy scheduling algorithm wherein multicast packets are stored in a first come first served fashion and have priority over unicast queues and steps in I th time slot further comprise: choosing all outputs j such that jxcex5Ok(i,1)∩BMi at input i, 0xe2x89xa6ixe2x89xa6Nxe2x88x921 and transmitting HOL multicast packets the chosen outputs in the kth time slot. serving unicast queues if Ok(i,I)∩BMi is an empty set, otherwise excluding the chosen outputs are from Ok(i,I) and BMi.; and deleting HOL multicast packets from the multicast queue If BMi is empty.
Another aspect of the present invention is a method of pipelined round robin greedy scheduling for even number of inputs wherein an Th time slot is completed using a process comprising: initializing k(0,1)=k(1,1)= . . . k(Nxe2x88x921,1)=0, const N+1, wherein, k(i,l) greater than 0 is the time slot for which input i reserves an output in lth time slot, it=(constxe2x88x92Nxe2x88x921) mod N denotes an input that starts a new schedule in lth time slot, and k(i,I)=0 implies that the action of input i in time slot l is suppressed; setting OI+N={O,1, . . . ,Nxe2x88x921}, k(il,I)=l+N+1, k(mod(iI+l) mod N,l)=k(iIIxe2x88x922), and k(i,l)=k((ixe2x88x921) mod N,Ixe2x88x921) for 0xe2x89xa6ixe2x89xa6Nxe2x88x921 and(i1+1)mod N} and I is not equal to It3; choosing one output j at input i, 0xe2x89xa6ixe2x89xa6Nxe2x88x921, in a round-robin fashion from the set Ok(i,l) for which it has a packet to send, provided that k(i, l)xe2x89xa00 and excluding j from Ok(i,l); storing the address, at input i, 0xe2x89xa6ixe2x89xa6Nxe2x88x921, of the chosen output in its connection memory at location k(i, l)mod (N+1) and moving an HOL packet from a corresponding receive input-output queue to separate transmit input-output queue; forwarding the set Ok(i,I) at Input i, 0xe2x89xa6ixe2x89xa6Nxe2x88x921 and i=(ilxe2x88x922)mod N, to the next input (i+1)mod N, wherein Input (i1xe2x88x922)mod N delays the set Ok((xe2x88x922)mod N,1) for one time slot before forwarding it; establishing a cross bar connection between the input i 0xe2x89xa6ixe2x89xa6Nxe2x88x921 and output whose address is read from location (l mod(N+1)) of the input i""s connection memory; transmitting the reserved packet at the head of the scheduled transmit input-output queue is transmitted through the switch core for each input i, 0xe2x89xa6ixe2x89xa6Nxe2x88x921.
Preferably multicast scheduling is incorporated in round-robin greedy scheduling algorithm wherein multicast packets are stored in a first come first served fashion and have priority over unicast queues and steps in lth time slot further comprise: choosing all outputs j such that jxcex5Ok(i,I)∩BMi at input i, 0xe2x89xa6ixe2x89xa6Nxe2x88x921 and transmitting HOL multicast packets to the chosen outputs in the kth time slot; serving unicast queues if Ok(i,I)∩BMi is an empty set, otherwise excluding the chosen outputs are from Ok(i,I) and BMi; deleting HOL multicast packets from the multicast queue If BMi is empty.
Another aspect of the present invention is a N stage pipeline system for scheduling a Nxc3x97N switch where a stage i is associated with an input i, said stage i schedules transmission to an output in a future time slot, said future time slot rippling through all stages, wherein all pipeline stages corresponding to inputs are performing scheduling concurrently such that no two inputs choose a same future time slot at a same time, output slots being selected based on a round-robin fashion, wherein when an output is selected by a stage, the output is removed from a free pool of outputs such that a pipeline stage does not pick the output that has already been selected during a time slot.